package day03;

public class MyHashMap<K, V> {
    private Node<K, V>[] table;
    private int size;
    private float loadFactor = 0.75f;
    private int threshold;

    private class Node<K, V>{
        K key;
        V value;
        Node<K, V> next;
        public Node(K key, V value){
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value + '}';
        }
    }

    /**
     * 重新散列算法
     * - 简单当前数据量是否达到门槛, 如果达到门槛, 就扩容重新散列元素
     */
    public void resize(){
//        if(size != threshold){
//            return;
//        }
        //创建一个新数组, 容器是原数组的两倍
        Node<K, V>[] tbl = new Node[table.length<<1];
        for (int i=0; i<table.length; i++){
            if(table[i]==null){
                continue;
            }
            //可能是散列桶, 遍历散列桶
            Node<K, V> node = table[i];
            do{
                //node 就是散列表中每个Node元素
                //将 node 添加到新的 tbl 中
                putValue(node.key, node.value, tbl);
                // System.out.println(node);
                node = node.next;
            }while (node != null);
        }
        //用新数组替换原数组
        table = tbl;
        //调整下次扩容的门槛值
        threshold = (int)(tbl.length * loadFactor);
    }

    /**
     * 将 key value 添加的新的数组 tbl 中
     * @param key 原有的 key
     * @param value 原有的 value
     * @param tbl 新数组
     */
    private void putValue(K key, V value, Node<K, V>[] tbl){
        int index = hash(key);
        if (tbl[index]==null) {
            tbl[index] = new Node<>(key, value);
        }else{
            Node<K,V> node = tbl[index];
            while (! key.equals(node.key)){
                if (node.next == null){
                    node.next = new Node<>(key, value);
                }
                node = node.next;
            }
        }
    }

    public V put(K key, V value){
        if(size == 0){
            table = new Node[16];
            threshold = (int)(table.length * loadFactor);
        }
        int index = hash(key);
        if (table[index]==null) {
            table[hash(key)] = new Node<>(key, value);
            size++;
            if (size > threshold) {
                resize();
            }
            return null;
        }else{
            Node<K,V> node = table[index];
            while (! key.equals(node.key)){
                if (node.next == null){
                    node.next = new Node<>(key, value);
                    size++;
                    if (size > threshold) {
                        resize();
                    }
                    return null;
                }
                node = node.next;
            }
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }
    }
    private int hash(K key){
        int h = key.hashCode();
        return (h ^ (h >>> 16)) & (table.length-1);
    }
    public V get(K key){
        Node<K, V> node = table[hash(key)];
        while (! key.equals(node.key)){
            if (node.next == null){
                return null;
            }
            node = node.next;
        }
        return node.value;
    }

    @Override
    public String toString() {
        if (size == 0) {
            return "{}";
        }
        StringBuilder builder = new StringBuilder("{");
        for (int i=0; i<table.length; i++){
            if(table[i]==null){
                continue;
            }
            //可能是散列桶, 遍历散列桶
            Node<K, V> node = table[i];
            do{
                //node 就是散列表中每个Node元素
                builder.append(node.key).append("=")
                        .append(node.value).append(", ");
                node = node.next;
            }while (node != null);
        }
        return builder.delete(builder.length()-2, builder.length())
                .append("}").toString();
    }
}
